/**
 * 高效的双端队列实现，使用循环缓冲区优化性能
 * 支持 O(1) 时间复杂度的 push 和 shift 操作
 * 
 * @template T 队列中元素的类型
 */
export default class CircularDeque<T> {
    private buffer: (T | null)[];
    private head: number = 0;
    private tail: number = 0;
    private count: number = 0;

    /**
     * 创建循环双端队列
     * @param capacity 队列的最大容量
     */
    constructor(public readonly capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be greater than 0");
        }
        this.buffer = new Array(capacity).fill(null);
    }

    /**
     * 向队列尾部添加元素
     * 如果队列已满，会自动移除头部元素
     * @param item 要添加的元素
     */
    push(item: T): void {
        // 如果队列已满，先移除最旧的项目
        if (this.count === this.capacity) {
            this.shift();
        }
        
        this.buffer[this.tail] = item;
        this.tail = (this.tail + 1) % this.capacity;
        this.count = Math.min(this.count + 1, this.capacity);
    }

    /**
     * 从队列头部移除并返回元素
     * @returns 移除的元素，如果队列为空则返回 null
     */
    shift(): T | null {
        if (this.count === 0) return null;
        
        const item = this.buffer[this.head];
        this.buffer[this.head] = null; // 清除引用，避免内存泄漏
        this.head = (this.head + 1) % this.capacity;
        this.count--;
        
        return item;
    }

    /**
     * 清空队列
     */
    clear(): void {
        this.buffer.fill(null);
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }

    /**
     * 将队列转换为数组（按先进先出顺序）
     * @returns 包含队列所有元素的数组
     */
    toArray(): (T | null)[] {
        const result: (T | null)[] = [];
        for (let i = 0; i < this.count; i++) {
            const index = (this.head + i) % this.capacity;
            result.push(this.buffer[index]);
        }
        return result;
    }

    /**
     * 获取队列中的元素数量
     */
    get length(): number {
        return this.count;
    }

    /**
     * 检查队列是否为空
     */
    get isEmpty(): boolean {
        return this.count === 0;
    }

    /**
     * 检查队列是否已满
     */
    get isFull(): boolean {
        return this.count === this.capacity;
    }

    /**
     * 获取队列头部的元素（不移除）
     */
    peekFront(): T | null {
        if (this.isEmpty) return null;
        return this.buffer[this.head];
    }

    /**
     * 获取队列尾部的元素（不移除）
     */
    peekBack(): T | null {
        if (this.isEmpty) return null;
        const index = (this.tail - 1 + this.capacity) % this.capacity;
        return this.buffer[index];
    }
}